package myjava.algorithm.leetcode;

public class GasStation {

	public static int canCompleteCircuit(int[] gas, int[] cost) {
		int result = 0;
		
		int[] diff = new int[gas.length];
		
		
		for(int i=0;i<gas.length;i++)
		{
			diff[i] = gas[i]-cost[i];
			result += diff[i];
		}
		
		if(result < 0) return -1;
		
		int sum = 0, maxSum = 0, index = 0;
		
		for(int i=0;i<gas.length;i++)
		{
			sum += diff[i];
			
			if(maxSum < sum)
				maxSum = sum;
			else if(sum < 0)
			{
				sum = 0; // reset sum to restart
				index = i + 1; // move i forward to i+1.
			}
		}
		

		return index;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] gas =  {4};//	{1,2};
		int[] cost = {5};//{2,1};
		
		System.out.println(canCompleteCircuit(gas,cost));
	}

}
